
                 		BARAJ Clasa a X a

1. Harta unei paduri este reprezentata ca o matrice de nxm (n,m<31). Pe harta
sunt reprezentati arbori prin valoarea 1, atribuita pozitiilor acestora,
iar locurile neocupate sunt reprezentate prin valoarea 0. 
Dintr-un fisier text se citesc
n m
de pe prima linie, iar apoi de pe urmatoarele n linii se citesc cate m valori
0 sau 1, despartite de spatii, care definesc harta padurii. 
 Harta se modifica dupa una dintre regulile specificate in continuare.
	(i) Evolutia are loc in etape succesive astfel: daca la etapa curenta 
un arbore are cel putin doua pozitii vecine (dintre cele patru: sus, jos, 
stinga, dreapta) ocupate de cite un arbore atunci acesta rezista si in etapa 
urmatoare, altfel dispare. Pe un loc neocupat la etapa curenta poate sa creasca
un arbore in etapa urmatoare daca locul este inconjurat la etapa curenta de
cel putin doua pozitii vecine ocupate cu cite un arbore. Evolutia se termina
intr-o anumita etapa daca 
(a) fie toate pozitiile sunt ocupate 
(b) fie harta coincide cu cea a etapei anterioare. 
	Daca dupa 10 etape nu se ajunge in unul dintre cazurile (a) sau (b),
atunci evolutia se considera neterminata si se da mesajul EVOLUTIE NETERMINATA.
Etapa initiala corespunde hartii citite din PADURE.IN1 si este considerata 
etapa numarul 0. 
Intr-un fisier PADURE.O1 trebuie scrisa harta ultimei etape, numarul 
acesteia si unul dintre mesajele
POZITII OCUPATE		pentru situatia (a)
BLOCAJ 			pentru situatia (b) sau
EVOLUTIE NETERMINATA	altfel
	(ii) Avem la dispozitie un numar suficient de mare de padurari
astfel incit acestia sa poata defrisa padurea dupa regula: un padurar poate
taia doar arborii care se afla pe aceeasi linie sau coloana cu acesta (dar nu
se afla pe o pozitie ocupata de un arbore) si daca intre arbori si padurar nu 
se afla alti arbori. Orice padurar poate executa o singura etapa de taiere; la 
o asemenea etapa pot fi taiati 1-4 arbori.
Se cere ca pentru datele citite din PADURE.IN2 cu formatul
n m
de pe prima linie, iar apoi de pe urmatoarele n linii se citesc cate m valori
0 sau 1, despartite de spatii, care definesc harta padurii, sa se scrie in 
PADURE.O2 numarul minim de padurari care pot defrisa padurea si pe liniile 
urmatoare pozitiile acestora in ordinea in care s-au asezat. 
(Timpul maxim de rezolvare pentru acest punct este 30 s)

Fiecare dintre cele 2 cerinte se noteaza cu cate 10 puncte.


2. Se considera o foaie avind cu un caroiaj de 1024x1024 celule patrate. 
Cele 512x512 din stinga-sus
se codifica cu a, cele din dreapta-sus cu b, cele din dreapta-jos cu c, iar
ultimele, cele din stinga-jos cu d. Operatia continua apoi in fiecare dintre
cele patru zone prin impartirea acestora in cite patru subzone codificate
dupa acelasi principiu si identificate de codul obtinut prin concatenare. 
De exemplu

1   |---------|--------|
    | aa | ab |        |
256 |---------|    b   |
    | ad | ac |        |
512 |---------|--------|
    |         |        |
    |    d    |    c   |
    |         |        |
1024|---------|--------|

Operatia continua pina se codifica fiecare celula cu coduri distincte. 
(i) Dindu-se un cod sub forma x_1x_2...x_p, sa se precizeze, in cazul
in care reprezinta codul unei subzone din caroiaj, coordonatele celulelor
subzonei care ocupa extremitatile din stinga-sus si dreapta-jos. De exemplu
pentru aa, coordonatele sunt 1 1 256 256.
Sirul reprezentind codul se citeste dintr-un fisier CELULE.IN1, iar in CELULE.O1
se scrie pe o linie mesajul
SIR INCORECT
daca nu exista subzona identificata, sau 
n m q r
reprezentind coordonatele subzonei, despartite prin spatii.

(ii) Foia data poate fi pliata dupa patru directii, doua relative la axa
de simetrie verticala si doua relative la cea orizontala pe care le notam
	1 - stinga peste dreapta
	2 - dreapta peste stinga
	3 - sus peste jos
	4 - jos peste sus.
De exemplu daca se executa 1 atunci celula de coordonate (1,1) se aseaza peste
cea de coordonate (1,1024), in cazul 2 acestea se aseaza invers, iar pentru 3
(1,1) vine peste (1024,1). Vom numi file fiecare din partile foii evidentiate
prin pliere.
	(ii.1) Din fisierul CELULE.IN2 se citesc de pe prima linie o succesiune
de plieri, nedespartite prin spatii, c_1c_2...c_k unde c_i apartine multimii 
{1,2,3,4}; iar de pe a doua linie codul unei celule x_1x_2...x_10, unde x_i 
apartine multimii {a,b,c,d}. Sa se scrie in fisierul CELULE.O2 numarul filei 
ce contine celula de cod specificat, convenind sa notam cu 1 fila de la baza.
	(ii.2) De pe urmatoarele k+1 linii din fisierul CELULE.IN2 se citesc 
valoarea k  reprezentand k plieri arbitrare si apoi 2^k linii, fiecare avind 
codul celulei care ocupa pozitia din stinga-sus din fila curenta; filele sunt 
parcurse de la baza catre virf. 
In fisierul CELULE.O2 se va scrie o succesiune
c_1c_2...c_k
corespunzind operatiilor de pliere care trebuie executate pentru a obtine
asezarea ceruta a filelor. In cazul in care nu exista solutie, in fisier
este scris mesajul
PLIERE IMPOSIBILA

Fiecare dintre cele 3 cerinte se noteaza cu cate 10 puncte.


Timp de lucru pentru ambele probleme: 3 ore.